/*  sffffadd.cpp  by K.Tsuru  */
// function ID = 710  DRADIX
/******************************************************************
SFraction class
It provides the addition "m+n".
(x.num/x.den)+(y.num/y.den)
= (x.num*y.den+y.num*x.den)/(x.den*y.den)                 (1)
= (x.num*(y.den/d1)+y.num*(x.den/d1)/((x.den/d1)*y.den)   (2)
The method (2) is the Knuth's one.This method is faster than
the method (1).The method (3) the reduction is leaved until
 the number of figures exceed a threshold
For example in the calculation using Pentium 120MHz
  1/0! + 1/1! + 1/2! + .... 1/100!
(1) 9.0 sec, (2) 7.1 sec, (3) less than 2.0 sec.

However by updating hardware and compiler the method (2) becomes fastest.
Then I adopt Knuth's method(2).
ref: The Art of Computer Programing VOLUME 2 pp.330-331
*******************************************************************/

#ifndef SN_H
#include "sn.h"
#endif

SFraction FFAdd(const SFraction& x, const SFraction& y){
    SFraction z;
#if REDUCE_SIZE==0 //use Knuth's method
    SLong d1, d2, t, xd1;

    d1 = gcdL(x.den, y.den);  // gcd
    if(d1.IsOne()) {    // d1 == 1
        z.den = x.den*y.den;
        z.num = x.num*y.den + y.num*x.den;
    } else {
        xd1 = x.den/d1;
        t = x.num*(y.den/d1) + y.num*xd1; // numerator
        d2 = gcdL(t, d1);
        if(d2.IsOne()){
            z.den = xd1*y.den;
            z.num = t;
        } else {
            z.den = xd1*(y.den/d2);
            z.num = t/d2;
        }
    }
    if( !z.num.Sign(710) ) z.den.SetShort(1);      //zero
#ifndef NDEBUG
    assert(z.den.Sign(710) > 0);
#endif
    z.reduceDone = true;
    return z;
#else //REDUCE_SIZE!=0
    if(x.ReduceStepByStep()) {//use Knuth's method
        SLong d1, d2, t, xd1;

        d1 = gcdL(x.den, y.den);  // gcd
        if(d1.IsOne()) {    // d1 == 1
            z.den = x.den*y.den;
            z.num = x.num*y.den + y.num*x.den;
        } else {
            xd1 = x.den/d1;
            t = x.num*(y.den/d1) + y.num*xd1; // numerator
            d2 = gcdL(t, d1);
            if(d2.IsOne()){
                z.den = xd1*y.den;
                z.num = t;
            } else {
                z.den = xd1*(y.den/d2);
                z.num = t/d2;
            }
        }
        if( !z.num.Sign(710) ) z.den.SetShort(1);      //zero
#ifndef NDEBUG
    assert(z.den.Sign(710) > 0);
#endif
        z.reduceDone = true;
        return z;
    } else {
        z.den = x.den*y.den;
        z.num = x.num*y.den + y.num*x.den;
        z.reduce(false);
        return z;
    }
#endif
}